//
// Created by ASUS on 2024/12/20/星期五.
//
#include <vector>
#include <iostream>
using namespace std;

struct Node {
	int sum;
	Node *left, *right;
	Node(int s = 0) : sum(s), left(nullptr), right(nullptr) {}
};

class PersistentSegmentTree {
private:
	vector<Node*> roots;
	int n;

	Node* buildTree(int start, int end) {
		if (start == end) {
			return new Node();
		}
		int mid = (start + end) / 2;
		Node* node = new Node();
		node->left = buildTree(start, mid);
		node->right = buildTree(mid + 1, end);
		return node;
	}

	Node* updateTree(Node* prev, int start, int end, int idx, int val) {
		if (start == end) {
			return new Node(prev->sum + val);
		}
		int mid = (start + end) / 2;
		Node* node = new Node();
		if (idx <= mid) {
			node->left = updateTree(prev->left, start, mid, idx, val);
			node->right = prev->right;
		} else {
			node->left = prev->left;
			node->right = updateTree(prev->right, mid + 1, end, idx, val);
		}
		node->sum = node->left->sum + node->right->sum;
		return node;
	}

	int queryTree(Node* node, int start, int end, int L, int R) {
		if (R < start || end < L) {
			return 0;
		}
		if (L <= start && end <= R) {
			return node->sum;
		}
		int mid = (start + end) / 2;
		return queryTree(node->left, start, mid, L, R) + queryTree(node->right, mid + 1, end, L, R);
	}

public:
	PersistentSegmentTree(vector<int>& nums) {
		n = nums.size();
		roots.push_back(buildTree(0, n - 1));
		for (int i = 0; i < n; ++i) {
			roots.push_back(updateTree(roots.back(), 0, n - 1, i, nums[i]));
		}
	}

	void update(int version, int idx, int val) {
		roots.push_back(updateTree(roots[version], 0, n - 1, idx, val));
	}

	int query(int version, int L, int R) {
		return queryTree(roots[version], 0, n - 1, L, R);
	}
};

int main() {
	vector<int> nums = {1, 3, 5, 7, 9, 11};
	PersistentSegmentTree segTree(nums);

	cout << "Sum of values in given range in version 0 = " << segTree.query(0, 1, 3) << endl;

	segTree.update(0, 1, 10);

	cout << "Sum of values in given range in version 1 = " << segTree.query(1, 1, 3) << endl;

	return 0;
}